#include "single_list.h"

#include <stdlib.h>
#include <string.h>

static int SListDefaultCompare(single_list_node_t* node1, single_list_node_t* node2)
{
    if (node1 == node2)
    {
        return 0;
    }
    else if (node1 < node2)
    {
        return -1;
    }

    return 1;
}

single_list_t* SListCreate()
{
    single_list_t* sl = (single_list_t*)malloc(sizeof(single_list_t));

    if (sl)
    {
        memset(sl, 0, sizeof(single_list_t));
    }

    return sl;
}


void SListDestroy(single_list_t* sl)
{
    if (sl)
    {
        SListClear(sl);
        free(sl);
    }
}

void SListClear(single_list_t* sl)
{
    if (sl)
    {
        single_list_node_t* tmp = sl->head;
        /**if not set user customer node free function, then use std c api: free */
        void(*NodeFree)(void* node) = (sl->nodeFree != NULL) ? sl->nodeFree : free;

        single_list_node_t* next = NULL;
        while (tmp != NULL)
        {
            next = tmp->next;
            NodeFree(tmp);
            tmp = next;
        }

        sl->head = NULL;
        sl->tail = NULL;
        sl->node_count = 0;
    }
}

bool SListIsEmpty(single_list_t* sl)
{
    return (sl == NULL) ? false : (sl->node_count == 0);
}

uint32_t SListLength(single_list_t* sl)
{
    return (sl == NULL) ? 0 : sl->node_count;
}

single_list_t* SListPushBack(single_list_t* sl, single_list_node_t* node)
{
    if ((sl == NULL) || (node == NULL))
    {
        return sl;
    }

    if (sl->head == NULL) /** mean thar current push node is first node */
    {
        sl->head = node;
        sl->tail = node;
    }
    else
    {
        sl->tail->next = node;
        sl->tail = node;
    }

    sl->node_count++;
    return sl;
}

single_list_t* SListPushFront(single_list_t* sl, single_list_node_t* node)
{
    if ((sl == NULL) || (node == NULL))
    {
        return sl;
    }


    if (sl->head == NULL) /** mean thar current push node is first node */
    {
        sl->head = node;
        sl->tail = node;
    }
    else
    {
        node->next = sl->head;
        sl->head = node;
    }

    sl->node_count++;
    return sl;
}

void SListPopFront(single_list_t* sl)
{
    if (sl && sl->head)
    {
        single_list_node_t* tmp = sl->head->next;
        /**if not set user customer node free function, then use std c api: free */
        void(*NodeFree)(void* node) = (sl->nodeFree != NULL) ? sl->nodeFree : free;
        NodeFree(sl->head);
        sl->head = tmp;

        if (tmp == NULL) /**mean that the list is empty now, so reset tail node */
        {
            sl->tail = NULL;
        }

        sl->node_count--;
    }
}

/** @brief insert 'node' after 'pos'
 * success: true, else: false

 */
bool SListInsert(single_list_t* sl, single_list_node_t* pos, single_list_node_t* node)
{
    if ((sl == NULL) || (pos == NULL) || (node == NULL) || (pos == node))
    {
        return false;
    }
    
    node->next = pos->next;
    pos->next = node;
    
    if (pos == sl->tail)
    {/** if pos is tail node, then change really tail node */
        sl->tail = node;
    }
    
    sl->node_count++;

    return true;
}

bool SListRemove(single_list_t* sl, single_list_node_t* pos, single_list_node_t* node)
{
    if ((sl == NULL) || (pos == NULL) || (node == NULL) || (pos == node) || (pos->next != node))
    {
        return false;
    }

    pos->next = node->next;

    /**if not set user customer node free function, then use std c api: free */
    void(*NodeFree)(void* node) = (sl->nodeFree != NULL) ? sl->nodeFree : free;
    NodeFree(node);

    if (node == sl->tail) /** if tail node is removed,then change really tail node */
    {
        sl->tail = pos;
    }

    sl->node_count--;

    return true;
}

bool SListErase(single_list_t* sl, single_list_node_t* node)
{
    if ((sl == NULL) || (node == NULL))
    {
        return false;
    }

    single_list_node_t* prev = sl->head;
    single_list_node_t* next = prev;

    /**if not set user customer node free function, then use std c api: free */
    void(*NodeFree)(void* node) = (sl->nodeFree != NULL) ? sl->nodeFree : free;

    while (next)
    {
        if (next == node)
        { 
            if (next == sl->head)
            {/** mean that erase first node */
                sl->head = next->next;

                if (next == sl->tail)
                {/** mean that list only 1 node */
                    sl->tail = NULL;
                }
            }
            else if (next == sl->tail)
            { /** mean that erase tail node and list more than 1 node */
                sl->tail = prev;
            }
            else
            {/**mean that erase the middle of list and list more than 2 node */
                prev->next = node->next;
            }
            
            NodeFree(node);
            sl->node_count--;

            return true;
        }

        prev = next;
        next = next->next;
    }

    return false;
}

single_list_node_t* SListFind(single_list_t* sl, single_list_node_t* target)
{
    if ((sl == NULL) || (target == NULL))
    {
        return NULL;
    }

    /**if not set user customer node free function, then use std c api: free */
    int(*NodeCompare)(single_list_node_t * node1, single_list_node_t * node2) = (sl->compare != NULL) ? sl->compare : SListDefaultCompare;
    single_list_node_t* tmp = sl->head;
    while (tmp)
    {
        if (NodeCompare(tmp, target) == 0)
        {
            return tmp;
        }
    }

    return NULL;
}

single_list_node_t* SListAt(single_list_t* sl, uint32_t index)
{
    if ((sl == NULL) || (sl->node_count < index))
    {
        return NULL;
    }

    single_list_node_t* tmp = sl->head;
    while (index > 0)
    {
        tmp = tmp->next;
        index--;
    }

    return tmp;
}

single_list_t* SListRewind(single_list_t* sl)
{
    if ((sl == NULL) || (sl->node_count < 2))
    {/** only node more than 2, then rewind take effect. */
        return sl;
    }

    single_list_node_t* prev = sl->head;
    single_list_node_t* next = prev->next;
    single_list_node_t* tmp = NULL;

    while (next)
    {
        tmp = next->next;
        next->next = prev;
        prev = next;
        next = tmp;
    }

    tmp = sl->head;
    sl->head = sl->tail;
    sl->tail = tmp;

    return sl;
}

/**true: have cycle, false: haven't
 * slow and fast pointer
 */
bool SListCycleCheck(single_list_t* sl)
{
    if ((sl == NULL) || (sl->node_count < 2))
    {/** only node more than 2, then maybe have cycle. */
        return false;
    }

    single_list_node_t* slowPtr = sl->head;
    single_list_node_t* fastPtr = sl->head->next;
    while (fastPtr && fastPtr->next)
    {
        if (slowPtr == fastPtr)
        {
            return true;  /**then, indicate have cycle */
        }

        slowPtr = slowPtr->next;
        fastPtr = fastPtr->next->next;
    }

    return false;
}


/**true: have cycle, false: haven't
 * use list counter,foreach list, if step count > list->length, then have cycle
 */
bool SListCycleFastCheck(single_list_t* sl)
{
    if ((sl == NULL) || (sl->node_count < 2))
    {/** only node more than 2, then maybe have cycle. */
        return false;
    }

    single_list_node_t* tmp = sl->head;
    uint32_t loopCnt = 0;
    while (tmp)
    {
        if (loopCnt > sl->node_count)
        {
            return true; /**then have cycle */
        }
        tmp = tmp->next;
        loopCnt++;
    }

    return false;
}

single_list_t* SListMerge(single_list_t* sl1, single_list_t* sl2)
{
    if ((sl1 == NULL) || (sl2 == NULL))
    {
        return NULL;
    }
    single_list_t* newsl = SListCreate();

    single_list_node_t* node1 = sl1->head;
    single_list_node_t* node2 = sl2->head;
    /**if not set user customer node free function, then use std c api: free */
    int(*NodeCompare)(single_list_node_t * node1, single_list_node_t * node2) = (sl1->compare != NULL) ? sl1->compare : SListDefaultCompare;

    while (node1 || node2)
    {

        if (NodeCompare(node1, node2) == 1) /** node1 > node2, then add node2 frist */
        {
            SListPushBack(newsl, node2);
            SListPushBack(newsl, node1);
        }
        else
        {
            SListPushBack(newsl, node1);
            SListPushBack(newsl, node2);
        }

        node1 = node1 ? node1->next : NULL;

        node2 = node2->next;
    }

    SListDestroy(sl1);
    SListDestroy(sl2);

    return newsl;
}

/**Delete the penultimate nth node of the linked list, n is the index start from list tail */
bool SListDeleteBack(single_list_t* sl, uint32_t n)
{
    if ((sl == NULL) || (sl->node_count < n))
    {
        return false;
    }

    single_list_node_t* start = sl->head;
    single_list_node_t* tail = sl->head;
    single_list_node_t* prev = NULL;
    while (tail && (n > 0))
    {
        tail = tail->next;
        n--;
    }

    while (tail && tail->next)
    {
        start = start->next;
        tail = tail->next;
    }

    if (start)
    {
        single_list_node_t* next = start->next;     /** target */

        start->next = next ? next->next: NULL;
        return true;
    }

    return false;    

}

single_list_node_t* SListGetMiddleNode(single_list_t* sl)
{
    if ((sl == NULL) || (sl->node_count < 2))
    {
        return NULL;
    }

    single_list_node_t* slowPtr = sl->head;
    single_list_node_t* fastPtr = sl->head;

    while (fastPtr && fastPtr->next)
    {
        slowPtr = slowPtr->next;
        fastPtr = fastPtr->next->next;
    }

    return slowPtr;
}

void SListForeach(single_list_t* sl, void(*opt)(single_list_node_t* node, uint32_t idx))
{
    if ((sl == NULL) || (opt == NULL))
    {
        return ;
    }
    single_list_node_t* tmp = sl->head;
    uint32_t idx = 0;
    while (tmp)
    {
        opt(tmp, idx);
        tmp = tmp->next;
        idx++;
    }
}

bool SListCheckPalindrome(single_list_t* sl)
{
    if ((sl == NULL) || (sl->node_count < 2) || (sl->compare == NULL))
    {
        return false;
    }

    single_list_node_t* prev = sl->head;
    single_list_node_t* next = SListGetMiddleNode(sl);
    /**if not set user customer node free function, then use std c api: free */
    int(*NodeCompare)(single_list_node_t * node1, single_list_node_t * node2) = sl->compare;


    while (next)
    {
        if (NodeCompare(prev, next) != 0)
        {
            return false;
        }
        prev = prev->next;
        next = next->next;
    }

    return true;
}